import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Demo0712
{
    public static void main(String[] args) {
        BinaryTree binaryTree=new BinaryTree();
        BinaryTree.TreeNode root=binaryTree.createTree();
       binaryTree.levelOrder(root);
    }

}
//判断一棵二叉树是否为平衡二叉树
class Solution {
    public int height(TreeNode root) {
        if(root==null) return 0;
        int leftheight=height(root.left);
        int rightheight=height(root.right);
        if(leftheight>=0 && rightheight>=0 && Math.abs(leftheight-rightheight)<=1 ){
            return Math.max(leftheight,rightheight)+1;
        }else{
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        if(height(root)>=1) return true;
        else return false;
    }


}


//另一棵树的子树
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q!=null || q==null && p!=null) return false;
        if(p==null && q==null)return true;
        if(p.val != q.val) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot){
        if(root==null || subRoot==null) return false;
        if(isSameTree(root,subRoot)) return true;
        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }
}
//对称二叉树
class Solution {
    public boolean isSymmetric2(TreeNode lefttree,TreeNode righttree) {
        if(lefttree==null && righttree==null) return true;
        if(lefttree==null || righttree==null ) return false;
        if(lefttree.val != righttree.val) return false;
        return isSymmetric2(lefttree.left,righttree.right) && isSymmetric2(righttree.left,lefttree.right);
    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return isSymmetric2(root.left,root.right);
    }
}
//检查两棵树是否相同
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q!=null || q==null && p!=null) return false;
        if(p==null && q==null)return true;
        if(p.val != q.val) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}
//反转二叉树
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return root;
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(tmp);
        invertTree(root.left);
        return root;
    }
}



//二叉树实现与遍历
class Main{
    class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
            this.val=val;
        }
    }
    public int i=0;
    public TreeNode creatTree(String s){
        TreeNode root=null;
        if(s.charAt(i) != '#'){
            root=new TreeNode(s.charAt(i));
            i++;
            root.left=creatTree(s);
            root.right=creatTree(s);
        }else{
            i++;
        }
        return root;
    }
    public void DisplayNode(TreeNode root){
        if(root==null) return;
        DisplayNode(root.left);
        System.out.print(root.val+" ");
        DisplayNode(root.right);
    }
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        while(in.hasNext()){
            String s=in.nextLine();
            Main mainclass=new Main();
            TreeNode root=mainclass.creatTree(s);
            mainclass.DisplayNode(root);
        }
    }
}
//二叉树实现与遍历
//
//二叉树实现
class BinaryTree {

    static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }


    /**
     * 创建一棵二叉树 返回这棵树的根节点
     *
     * @return
     */
    public TreeNode createTree() {
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        return A;
    }
    public TreeNode createTree2() {
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        return A;
    }

    // 前序遍历
    public void preOrder(TreeNode root) {
        if(root==null) return;
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    void inOrder(TreeNode root) {
        if(root==null) return;
        preOrder(root.left);
        System.out.print(root.val+" ");
        preOrder(root.right);
    }

    // 后序遍历
    void postOrder(TreeNode root) {
        if(root==null) return;
        preOrder(root.left);
        preOrder(root.right);
        System.out.print(root.val+" ");
    }

    public static int nodeSize;

    /**
     * 获取树中节点的个数：遍历思路
     */
    void size(TreeNode root) {
        if(root==null) return;
        nodeSize++;
        size(root.left);
        size(root.right);
    }

    /**
     * 获取节点的个数：子问题的思路
     *
     * @param root
     * @return
     */
    int size2(TreeNode root) {
        if(root==null) return 0;
        return size2(root.left)+size2(root.right)+1;
    }


    /*
     获取叶子节点的个数：遍历思路
     */
    public static int leafSize = 0;

    void getLeafNodeCount1(TreeNode root) {
        if(root==null) return;
        if(root.left==null && root.right==null) leafSize++;
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    /*
     获取叶子节点的个数：子问题
     */
    int getLeafNodeCount2(TreeNode root) {
        if(root==null) return 0;
        if(root.left==null && root.right==null) return 1;
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }

    /*
    获取第K层节点的个数
     */
    int getKLevelNodeCount(TreeNode root, int k) {
        if(root==null) return 0;
        if(k==1) return 1;
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

    /*
     获取二叉树的高度
     时间复杂度：O(N)
     */
    int getHeight(TreeNode root) {
        if(root==null) return 0;
        int leftheight=getHeight(root.left);
        int rightheight=getHeight(root.right);
        return leftheight>rightheight?leftheight+1:rightheight+1;

    }


    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if(root==null) return null;
        if(root.val==val) return root;
        TreeNode ret1=find(root.left,val);
        TreeNode ret2=find(root.right,val);
        if(ret1!=null) return ret1;
        if(ret2!=null) return ret2;
        return null;
    }

    //层序遍历
    void levelOrder(TreeNode root) {
        Queue<TreeNode> myqueue=new LinkedList<>();
        myqueue.offer(root);
        while(!myqueue.isEmpty()){
            TreeNode cur=myqueue.poll();
            if(cur.left!=null) myqueue.offer(cur.left);
            if(cur.right!=null) myqueue.offer(cur.right);
            System.out.print(cur.val+" ");
        }
    }


    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> myqueue=new LinkedList<>();
        myqueue.offer(root);
        while(!myqueue.isEmpty()){
            TreeNode cur=myqueue.poll();
            if(cur!=null) {
                myqueue.offer(cur.left);
                myqueue.offer(cur.right);
            }else{
                break;
            }
        }
        while(!myqueue.isEmpty()){
            TreeNode cur=myqueue.poll();
            if(cur!=null) {
                return false;
            }
        }
        return true;
    }
}
//二叉树实现

//public boolean isSameTree(TreeNode p, TreeNode q) {
//        if(p == null && q != null || p != null && q == null) {
//            return false;
//        }
//        if(p == null && q == null) {
//            return true;
//        }
//        if(p.val != q.val) {
//            return false;
//        }
//        return isSameTree(p.left,q.left) && isSameTree(p.right,q.left);
//    }
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//       if(isSameTree(root,subRoot)){
//           return true;
//       }
//       if(isSameTree(root.left,subRoot)){
//           return true;
//        }
//        if(isSameTree(root.right,subRoot)){
//            return true;
//        }
//        return false;
//    }
//
//    public boolean isSymmetric(TreeNode root) {
//        if(root == null) {
//            return true;
//        }
//        return isSymmetricChild(root.left,root.right);
//    }
//
//    private boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
//         if(leftTree==null && rightTree!=null || leftTree!=null && rightTree==null){
//             return false;
//         }
//         if(leftTree==null || rightTree==null) return true;
//         if(leftTree.val!=rightTree.val) return flase;
//         return isSymmetric(leftTree) && isSymmetric(rightTree)
//    }//public boolean isSameTree(TreeNode p, TreeNode q) {
//        if(p == null && q != null || p != null && q == null) {
//            return false;
//        }
//        if(p == null && q == null) {
//            return true;
//        }
//        if(p.val != q.val) {
//            return false;
//        }
//        return isSameTree(p.left,q.left) && isSameTree(p.right,q.left);
//    }
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//       if(isSameTree(root,subRoot)){
//           return true;
//       }
//       if(isSameTree(root.left,subRoot)){
//           return true;
//        }
//        if(isSameTree(root.right,subRoot)){
//            return true;
//        }
//        return false;
//    }
//
//    public boolean isSymmetric(TreeNode root) {
//        if(root == null) {
//            return true;
//        }
//        return isSymmetricChild(root.left,root.right);
//    }
//
//    private boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
//         if(leftTree==null && rightTree!=null || leftTree!=null && rightTree==null){
//             return false;
//         }
//         if(leftTree==null || rightTree==null) return true;
//         if(leftTree.val!=rightTree.val) return flase;
//         return isSymmetric(leftTree) && isSymmetric(rightTree)
//    }//public boolean isSameTree(TreeNode p, TreeNode q) {
//        if(p == null && q != null || p != null && q == null) {
//            return false;
//        }
//        if(p == null && q == null) {
//            return true;
//        }
//        if(p.val != q.val) {
//            return false;
//        }
//        return isSameTree(p.left,q.left) && isSameTree(p.right,q.left);
//    }
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//       if(isSameTree(root,subRoot)){
//           return true;
//       }
//       if(isSameTree(root.left,subRoot)){
//           return true;
//        }
//        if(isSameTree(root.right,subRoot)){
//            return true;
//        }
//        return false;
//    }
//
//    public boolean isSymmetric(TreeNode root) {
//        if(root == null) {
//            return true;
//        }
//        return isSymmetricChild(root.left,root.right);
//    }
//
//    private boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
//         if(leftTree==null && rightTree!=null || leftTree!=null && rightTree==null){
//             return false;
//         }
//         if(leftTree==null || rightTree==null) return true;
//         if(leftTree.val!=rightTree.val) return flase;
//         return isSymmetric(leftTree) && isSymmetric(rightTree)
//    }//public boolean isSameTree(TreeNode p, TreeNode q) {
//        if(p == null && q != null || p != null && q == null) {
//            return false;
//        }
//        if(p == null && q == null) {
//            return true;
//        }
//        if(p.val != q.val) {
//            return false;
//        }
//        return isSameTree(p.left,q.left) && isSameTree(p.right,q.left);
//    }
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//       if(isSameTree(root,subRoot)){
//           return true;
//       }
//       if(isSameTree(root.left,subRoot)){
//           return true;
//        }
//        if(isSameTree(root.right,subRoot)){
//            return true;
//        }
//        return false;
//    }
//
//    public boolean isSymmetric(TreeNode root) {
//        if(root == null) {
//            return true;
//        }
//        return isSymmetricChild(root.left,root.right);
//    }
//
//    private boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
//         if(leftTree==null && rightTree!=null || leftTree!=null && rightTree==null){
//             return false;
//         }
//         if(leftTree==null || rightTree==null) return true;
//         if(leftTree.val!=rightTree.val) return flase;
//         return isSymmetric(leftTree) && isSymmetric(rightTree)
//    }